"""
2025.10.14
更新为循环链表
"""
class Linkedlist():
    class Node():
        def __init__(self, data=None):
            self.prev = None#双向链表
            self.data = data
            self.next = None

    def __init__(self):
        self.head = self.Node()#哨兵节点
        self.tail = self.head
        self.head.prev = self.tail
        self.size = 0
        self.max_node = self.size#防止循环链表死循环遍历
        
    def is_empty(self):
        return self.head.next is None

    def __len__(self):
        return self.size
    
    def show_list(self):
        if self.size == 0:
            return None
        cur_node = self.head.next
        #循环链表修改
        while cur_node and cur_node.next is not self.head:
            print(cur_node.data)
            cur_node = cur_node.next
        return True
    
    def append(self, value):
        """
        尾插法
        """
        newNode = self.Node(value)

        self.tail.next = newNode
        newNode.prev = self.tail
        self.tail = newNode
        #循环链表新增
        self.tail.next = self.head
        self.head.prev = self.tail
        self.size += 1

        return self        

    def prepend(self, value):
        """
        头插法
        """
        newNode = self.Node(value)
        newNode.next = self.head.next 
        if self.head.next is not None:
            self.head.next.prev = newNode
        newNode.prev = self.head
        self.head.next = newNode
        if self.tail == self.head:#如果是第一个节点
            self.tail = newNode
            #循环链表新增
            self.tail.next = self.head
            self.head.prev = self.tail
        self.size += 1
        return self
    
    def insert_at(self, index: int, value):
        """
        指定位置插入数据，头节点索引是0
        """
        if self.size -1 < index or index < 0:
            return False
        
        if index == 0:
            return self.prepend(value)
        elif self.size -1 == index:
            return self.append(value)

        cur_node = self.head.next
        for _ in range(index):
            cur_node = cur_node.next
        
        new_node = self.Node(value)
        new_node.next = cur_node.next
        new_node.prev = cur_node
        cur_node.next = new_node
        self.size += 1
        return self
    
    def delete_head(self):
        """
        删除头部节点
        """
        if self.size < 1:
            return False
        
        cur_node = self.head.next
        data = cur_node.data
        self.head.next = cur_node.next
        if cur_node.next is not None:
            self.head.next.prev = self.head
        self.size -= 1
        if self.size == 0:
            self.tail = self.head#更新尾节点

        return data
    
    def delete_tail(self):
        """
        删除尾部节点
        """
        if self.size < 1:
            return False
        
        data = self.tail.data
        self.tail = self.tail.prev
        #循环链表修改
        self.tail.next = self.head
        self.head.prev = self.tail
        self.size -= 1
        return data
    
    def remove_at(self, index: int):
        """
        删除指定位置数据，头节点索引是0
        """
        if self.size -1 < index or index < 0:
            return False

        if index == 0:
            return self.delete_head()
        elif self.size -1 == index:
            return self.delete_tail()

        cur_node = self.head.next
        #双向链表优化
        for _ in range(index):#index == 0不执行，即索引0直接headnext
            cur_node = cur_node.next

        cur_node.prev.next = cur_node.next
        cur_node.next.prev = cur_node.prev
        self.size -= 1
        return cur_node.data
    
    def remove_val(self, value):
        """
        删除链表中第一个指定值
        """
        pre_node = self.head
        while pre_node.next is not None:
            cur_node = pre_node.next
            if cur_node.data == value:
                pre_node.next = cur_node.next
                
                if pre_node.next is not None:
                    pre_node.next.prev = pre_node
                else:
                    self.tail = pre_node
                self.size -= 1
                return True
            pre_node = pre_node.next
        return False

    def peek_head(self):
        """
        获取头节点值
        """
        if self.size < 1:
            return None
        
        return self.head.next.data
    
    def peek_tail(self):
        """
        获取尾节点值
        """
        if self.size < 1:
            return None
        
        return self.tail.data
    
    def get_at(self, index: int):
        """
        获取指定节点值
        """
        if self.size <= index or index < 0:
            return None
        
        cur_node = self.head.next
        for _ in range(index):
            cur_node = cur_node.next

        return cur_node.data
    
    def contains(self, value):
        """
        检测是否包含某值
        """
        cur_node = self.head
        while cur_node.next != None:
            cur_node = cur_node.next
            if cur_node.data == value:
                return True
            
        return False
    
    def index_of(self, val):
        """
        找第一个符合值的索引
        """
        cur_node = self.head.next
        index = 0
        while cur_node:
            if cur_node.data == val:
                return index 
            cur_node = cur_node.next
            index += 1
        return -1
    
    #算法
    def reverse(self):
        """
        反转链表
        """
        if self.is_empty():
            return self
        
        old_first = self.head.next
        #方法1：新表遍历旧表尾插
    
        #方法2：原地反转
        prev = None
        cur_node = self.head.next
        while cur_node.next != None:
            temp_next = cur_node.next#临时记录
            cur_node.next = prev#指向上一个
            prev = cur_node#把自己变成prev
            cur_node = temp_next#指向原链表的下一个

        cur_node.next = prev#最后一个指向上一个
        self.head.next = cur_node
        self.tail = old_first
        return self

    def is_circular(self):
        """
        判断是否有环
        """
        if self.is_empty():
            return False
        
        slow = self.head.next
        fast = slow.next
        while slow is not fast:
            if fast == None or fast.next is None:
                return False
            fast = fast.next.next
            slow = slow.next
        return True
